package lhc.alg.top100;

import java.util.PriorityQueue;

/**
 * description: https://leetcode.cn/problems/find-median-from-data-stream/
 *  api解法。。。
 * author: hongchen.liao
 * date:  2022/8/18
 */
public class _295_Find_Median_from_Data_Stream {

    class MedianFinder {

        PriorityQueue<Integer> queMin;
        PriorityQueue<Integer> queMax;

        public MedianFinder() {
            queMin = new PriorityQueue<>((a, b)->(b - a));
            queMax = new PriorityQueue<>((a, b)->(a - b));
        }

        public void addNum(int num) {
            if(queMin.isEmpty() || num <= queMin.peek()){
                queMin.offer(num);
                if(queMax.size() + 1 < queMin.size()){
                    queMax.offer(queMin.poll());
                }
            }else{
                queMax.offer(num);
                if(queMax.size() > queMin.size()){
                    queMin.offer(queMax.poll());
                }
            }
        }

        public double findMedian() {
            if(queMin.size() > queMax.size()){
                return queMin.peek();
            }
            return (queMin.peek() + queMax.peek()) / 2.0;
        }
    }



}
